package trim.common.utils;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import trim.common.Format;
import trim.common.Material;
import trim.common.RejectedZone;
import trim.common.inputdata.FormatOrder;
import trim.common.inputdata.InputData;
import trim.common.inputdata.MaterialStock;

/**
 * Клас предназначенный для реализации часто исползуемых алгоритмов
 * Создан 27.05.2009 0:18:16
 * @author Дмитрий
 */
public class Utils
{

	private Utils()
	{
	}

	/**
	 * Интерфейс предназначенный лоя проверки найденного способа раскроя на допустимость его использования
	 */
	public static interface IValidator
	{

		/**
		 * Проверка допустимости способа раскроя
		 * @param pattern проверяемы способ раскроя
		 * @return true- раскрой допустим;false- в противном случае
		 */
		public boolean validate(int[] pattern);
	}

	/**
	 * Решение задачи нахождения наилучшего способа раскроя при заданных стоимостях форматов.
	 * Для решения используется метод ветвей и границ (Branch and bound (BB))
	 * @param formatLengths размеры форматов
	 * @param dualVars стоимости форматов
	 * @param n количество форматов для раскроя, используются первые n форматов
	 * (длины массивов не учитываюся)
	 * @param material раскраиваемый материал
	 * @param guardValue барьер, лучше котороги искать решение не обязательно
	 * @return способ раскроя с максимальной стоимостью
	 */
	public static int[] getBestPattern_BB(int[] formatLengths,double[] dualVars,int n,
					Material material,double guardValue)
	{
		return getBestPattern_BB(formatLengths,dualVars,n,material,guardValue,new IValidator()
		{

			@Override
			public boolean validate(int[] pattern)
			{
				return true;
			}
		});
	}

	/**
	 * Решение задачи нахождения наилучшего способа раскроя при заданных стоимостях форматов.
	 * Для решения используется метод ветвей и границ (Branch and bound (BB))
	 * @param formatLengths размеры форматов
	 * @param dualVars стоимости форматов
	 * @param n количество форматов для раскроя, используются первые n форматов
	 * (длины массивов не учитываюся)
	 * @param material раскраиваемый материал
	 * @param guardValue барьер, лучше котороги искать решение не обязательно
	 * @param v класс для проверки раскроя
	 * @return способ раскроя с максимальной стоимостью
	 */
	public static int[] getBestPattern_BB(int[] formatLengths,double[] dualVars,int n,
					Material material,double guardValue,IValidator v)
	{
		GenPatternData se=new GenPatternData();
		se.zones=material.getRejectedZones();
		se.zcount=se.zones.size();
		se.formatLengths=formatLengths;
		se.knifeCount=material.getKnifeCount();
		se.formatCount=n;
		int S=material.getLength()-material.getMinEdge()*2;
		se.effectiveWidth=S;
		se.knifeInterval=material.getKnifeInterval();
		se.dualVars=dualVars;
		double[] V=dualVars;
		int m;
		int lam;//небракованный остаток тамбура
		int xx[]=new int[n], xx1[]=new int[n];//решения
		int i, j, t;
		int Sort[]=new int[n];//массив индексов(для сортировки по возрастанию)
		int r[]=new int[n];
		se.currentPattern=xx;
		se.bestPattern=xx1;
		m=n;
		//сортировака фарматов по их удельной стоимости
		for(i=0;i<n;i++)
		{
			xx[i]=xx1[i]=0;
			Sort[i]=i;
			r[i]=0;
		}
		for(i=0;i<n-1;i++)
		{
			t=i;
			for(j=i+1;j<n;j++)
			{
				t=i;
				if((V[Sort[j]]/(double)formatLengths[Sort[j]])-(V[Sort[t]]/(double)formatLengths[Sort[t]])>1e-17)
				{
					t=j;
					m=Sort[i];
					Sort[i]=Sort[t];
					Sort[t]=m;
				}
			}
		}
		se.sort=Sort;
		se.m=n;
		//отбрасываем отрицательные элементы которые все находятся в конце массива
		while(se.m>0&&V[Sort[se.m-1]]<=-1e-9)
			se.m--;
		if(se.m==0)
			return r;
		if(se.zcount==0)
		{
			lam=0;
			genBestCol(se,0,S,0,0,lam,0,0,guardValue,v);
		}else
		{
			lam=S;
			for(RejectedZone rz:se.zones)
				lam-=Math.max(rz.getWidth(),se.knifeInterval);
			lam-=se.zones.get(0).getStart();
			genBestCol(se,0,se.zones.get(0).getStart(),0,0,lam,0,0,guardValue,v);
		}
		return se.bestPattern;
	}

	/**
	 * Решение задачи нахождения наилучшего способа раскроя при заданных стоимостях форматов.
	 * Для решения используется метод динамического программирования (Dynamic Programming (DP))
	 * @param formatLengths размеры форматов
	 * @param dualVars стоимости форматов
	 * @param n количество форматов для раскроя, используются первые n форматов
	 * (длины массивов не учитываюся)
	 * @param material раскраиваемый материал
	 * @param cutLength текущая стоимость (cutLength[длина_материала + 1])
	 * @param formatsCount текущее решение (formatsCount[длина_материала + 1][n])
	 * @return
	 */
	public static int[] getBestPattern_DP(int[] formatLengths,double[] dualVars,int n,
					Material material,double[] cutLength,int[][] formatsCount)
	{
		int[] initFormats=new int[n];
		int[] bestPattern=new int[n];

		int length=material.getLength();

		for(int i=0;i<n;i++)
		{
			initFormats[i]=material.getLength()/formatLengths[i];
		}

		for(int k=0;k<n;k++)
		{
			formatsCount[0][k]=initFormats[k];
		}

		for(int i=1;i<length+1;i++)
		{
			for(int k=0;k<n;k++)
			{
				formatsCount[i][k]=formatsCount[i-1][k];
			}
			cutLength[i]=cutLength[i-1];

			for(int k=0;k<n;k++)
			{
				if(i>=formatLengths[k])
				{
					if((cutLength[i]<dualVars[k]+cutLength[i-formatLengths[k]])&&(formatsCount[i-formatLengths[k]][k]>0))
					{
						cutLength[i]=dualVars[k]+cutLength[i-formatLengths[k]];

						for(int j=0;j<n;j++)
						{
							formatsCount[i][j]=formatsCount[i-formatLengths[k]][j];
						}

						formatsCount[i][k]=formatsCount[i-formatLengths[k]][k]-1;
					}
				}
			}
		}

		for(int i=0;i<n;i++)
		{
			bestPattern[i]=initFormats[i]-formatsCount[length][i];
		}

		return bestPattern;
	}

	/**
	 * Решение задачи нахождения наилучшего способа раскроя при заданных стоимостях форматов.
	 * Для решения используется метод динамического программирования (Dynamic Programming (DP))
	 * Учитывается количество ножей. 3 нижних массива вычищаются в самом методе.
	 * @param formatLengths длины форматов
	 * @param dualVariables вектор двойственных переменных
	 * @param dimension размерность
	 * @param material материал
	 * @param formats метки "откуда пришли" размерность должна быть material.getLength() + 1
	 * @param knifes метки "минимально возможное количество ножей" размерность должна быть material.getLength() + 1
	 * @param values метки "стоимость способы раскроя" размерность должна быть material.getLength() + 1
	 * @return способ раскроя с максимальной стоимостью
	 */
	public static int[] getBestPattern_DP_KC(int[] formatLengths,double[] dualVariables,int dimension,Material material,int[] formats,int[] knifes,double[] values)
	{
		int length=material.getLength();
		int knifeCount=material.getKnifeCount()-1;

		for(int i=0;i<=length;i++)
		{
			formats[i]=0;
			knifes[i]=0;
			values[i]=0.0;
		}

		for(int i=0;i<=length;i++)
		{
			for(int j=0;j<dimension;j++)
			{
				if(i+formatLengths[j]<=length)
				{
					if(values[i]+dualVariables[j]>values[i+formatLengths[j]])
					{
						values[i+formatLengths[j]]=values[i]+dualVariables[j];
						formats[i+formatLengths[j]]=j+1;
						knifes[i+formatLengths[j]]=knifes[i]+1;
					}
					if((values[i]+dualVariables[j]==values[i+formatLengths[j]])&&(knifes[i]+1<knifes[i+formatLengths[j]]))
					{
						formats[i+formatLengths[j]]=j+1;
						knifes[i+formatLengths[j]]=knifes[i]+1;
					}
				}
			}
		}

		int[] result=new int[dimension];

		for(int i=length;i>=0;i--)
		{
			if(knifes[i]<=knifeCount)
			{
				length=i;
				break;
			}
		}

		int i=formats[length];
		while(i>0)
		{
			result[i-1]++;
			length-=formatLengths[i-1];
			i=formats[length];
		}

		return result;
	}

	/**
	 * Решение задачи нахождения наиболее безотходного ракроя на данном типе материала,
	 * при ограничениях на количества форматов.
	 * Для решения используется метод ветвей и границ (Branches And Bounds (BB)).
	 * Метод по своей сути является ограниченной задачей о ранце (Bounded Knapsack Problem (BKP)).
	 * @param formatLengths размеры форматов
	 * @param formatRests остаток вектора требований
	 * @param material раскраиваемый материал
	 * @param formatCount количество форматов для раскроя, используются первые formatCount форматов
	 * (длины массивов не учитываюся)
	 * @return наиболее безотходный способ раскроя, при заданных ограничениях
	 */
	public static int[] getBoundedBestPattern_BB(int[] formatLengths,int[] formatRests,Material material,int formatCount)
	{
		int rest=material.getLength();
		int knifes=material.getKnifeCount();
		int count=0;

		int value=0;
		int record=0;

		int[] items=new int[formatCount];
		int[] bestItems=new int[formatCount];

		int[] indexes=new int[formatCount];

		int dimension=formatCount;

		int[] temp=new int[formatCount];

		for(int i=0;i<formatCount;i++)
		{
			if(formatRests[i]==0)
			{
				temp[i]=- 1;
				dimension--;
			}else
			{
				temp[i]=i;
			}
		}

		int next=0;

		indexes=new int[dimension];

		for(int i=0;i<formatCount;i++)
		{
			if(temp[i]!=- 1)
			{
				indexes[next]=i;
				next++;
			}
		}

		if(dimension==1)
		{
			bestItems[indexes[0]]=Math.min(rest/formatLengths[indexes[0]],formatRests[indexes[0]]);

			record=formatLengths[indexes[0]]*bestItems[indexes[0]];
		}else
		{
			int current=- 1;

			boolean exit=false;

			while(!exit)
			{
				while(true)
				{
					if(current==dimension-1)
					{
						break;
					}else
					{
						current++;
					}
					if((formatLengths[indexes[current]]<=rest)&&(items[indexes[current]]==0))
					{

						if(value+rest<=record)
						{
							break;
						}

						items[indexes[current]]=Math.min(rest/formatLengths[indexes[current]],formatRests[indexes[current]]);

						rest-=items[indexes[current]]*formatLengths[indexes[current]];
						value+=items[indexes[current]]*formatLengths[indexes[current]];
						count+=items[indexes[current]];

						if((record<value)&&(count<=knifes))
						{
							record=value;
							for(int i=0;i<dimension;i++)
							{
								bestItems[indexes[i]]=items[indexes[i]];
							}
						}
					}
				}

				while(true)
				{
					current--;

					if(items[indexes[current]]>0)
					{
						items[indexes[current]]--;
						rest+=formatLengths[indexes[current]];
						value-=formatLengths[indexes[current]];
						count--;

						break;
					}else
					{
						if(current==0)
						{
							exit=true;

							break;
						}
					}
				}
			}
		}

		return bestItems;
	}

	/**
	 * Генерация наилучшего способа раскроя
	 * @param se структура для хранения данных по генерируемому раскрою
	 * @param gam "стоимость" текущего раскроя
	 * @param zactiveWidth свободное место активной небракованной области
	 * @param zusedWidth пораченная область материала; при укладке слева на право -
	 * правая координата последнего уложенного формата. Форматы в области [0,zusedWidth]
	 * составляют стоимость gam
	 * @param zactive № активной небракованной области
	 * @param lam размер свободного пространства материала, который еще может быть использован.
	 * @param count количество уложенных на материал форматов
	 * @param cf (cf-1) последний уложенный формат
	 */
	private static void genBestCol(GenPatternData se,double gam,
					int zactiveWidth,int zusedWidth,int zactive,int lam,int count,int cf,double guardValue,IValidator v)
	{
		if(se.rec>guardValue+1e-6)
			return;
		if(gam>se.rec&&v.validate(se.currentPattern))
		{
			se.rec=gam;
			for(int i=0;i<se.formatCount;i++)
				se.bestPattern[i]=se.currentPattern[i];
		}
		for(int i=cf;i<se.m;i++)
		{
			if(se.formatLengths[se.sort[i]]>zactiveWidth)
				continue;
			//вычисление оценки
			double est;
			if(se.zcount==zactive)
				est=gam+(double)zactiveWidth*se.dualVars[se.sort[i]]/(double)se.formatLengths[se.sort[i]];
			else
			{
				RejectedZone z=se.zones.get(zactive);
				//[zusedWidth,t1]-свободная активная область для оценки
				int t1=Math.max(zusedWidth,se.knifeInterval>z.getWidth()?z.getStart()+z.getWidth()-se.knifeInterval:z.getStart());
				int t2=lam+z.getStart()-t1;
				est=gam+(double)(t1-zusedWidth)*se.dualVars[se.sort[i]]/(double)se.formatLengths[se.sort[i]]
								+(double)t2*se.dualVars[se.sort[0]]/(double)se.formatLengths[se.sort[0]];
			}
			if/*(est<guardValue+1e-6)*/(est<=se.rec)
				break;
			int t=(int)(zactiveWidth/se.formatLengths[se.sort[i]]);
			if((count+t)>=se.knifeCount)
				t=se.knifeCount-1-count;
			while(t>0)
			{
				se.currentPattern[se.sort[i]]+=t;
				genBestCol(se,gam+t*se.dualVars[se.sort[i]],
								zactiveWidth-t*se.formatLengths[se.sort[i]],
								zusedWidth+t*se.formatLengths[se.sort[i]],
								zactive,
								lam,
								count+t,i+1,guardValue,v);
				se.currentPattern[se.sort[i]]-=t;
				t--;
			}
		}
		if(zactive==se.zcount)
			return;

		RejectedZone z=se.zones.get(zactive);
		zusedWidth=Math.max(z.getWidth()+z.getStart(),zusedWidth+se.knifeInterval);
		zactive++;

		if(zactive==se.zcount)
		{
			zactiveWidth=se.effectiveWidth-zusedWidth;
			lam=0;
		}else
		{
			z=se.zones.get(zactive);
			zactiveWidth=z.getStart()-zusedWidth;
			lam-=z.getStart()-se.zones.get(zactive-1).getStart()-se.zones.get(zactive-1).getWidth();
		}

		genBestCol(se,gam,zactiveWidth,zusedWidth,zactive,lam,count,0,guardValue,v);
	}

	/**
	 *
	 * @param d
	 * @return
	 */
	public static InputData groupInputData(InputData d)
	{
		Map<Format,Integer> fmts=new HashMap();
		Map<Material,Integer> mtrls=new HashMap();
		for(MaterialStock ms:d.getMaterialStockList())
		{
			Integer i=mtrls.get(ms.getMaterial());
			if(i==null)
				mtrls.put(ms.getMaterial(),ms.getCount());
			else
				mtrls.put(ms.getMaterial(),ms.getCount()+i);
		}
		for(FormatOrder fo:d.getFormatOrderList())
		{
			Integer i=fmts.get(fo.getFormat());
			if(i==null)
				i=new Integer(0);
			fmts.put(fo.getFormat(),fo.getCount()+i);
		}
		InputData res=new InputData();
		for(Material m:mtrls.keySet())
		{
			res.getMaterialStockList().add(new MaterialStock(m,mtrls.get(m)));
		}
		for(Format f:fmts.keySet())
		{
			res.getFormatOrderList().add(new FormatOrder(f,fmts.get(f)));
		}
		return res;
	}

	private static class GenPatternData
	{

		double rec=Double.MIN_NORMAL;
		List<RejectedZone> zones;
		int zcount;
		int knifeInterval;
		int m;
		int sort[];
		int currentPattern[], bestPattern[];
		double dualVars[];
		int[] formatLengths;
		int formatCount;
		int knifeCount;
		int effectiveWidth;
	}
}
